import java.util.*;

class Solution {
    public int calculate(String str){
        return calculateRPN(RPN(str));
    }

    static Set<Character> operator = new HashSet<Character>() {{
        add('+');
        add('-');
        add('*');
        add('/');
    }};

    static Map<Character, Integer> operatorLevel = new HashMap<Character, Integer>() {{
        put('+', 0);
        put('-', 0);
        put('*', 1);
        put('/', 1);
        put('(', 2);
        put(')', 2);
    }};

    public static LinkedList<String> RPN(String str){
        if(str.charAt(0) == '-'){
            str = "0"+str;
        }
        str += "#";
        Stack<Character> ops = new Stack<>();
        LinkedList<String> output = new LinkedList<>();

        char[] chars = str.toCharArray();
        String tmp = ""; //临时存储数字
        for (int i=0;i<chars.length;i++){
            //判断负数的-号 (-2*3)，3--2 等，存入临时数字
            if(chars[i] == '-'){
                if (chars[i-1] == '(' || operator.contains(chars[i-1])){
                    tmp += '-';
                    continue;
                }
            }
            //判断数字，存入临时数字
            if(chars[i] >= '0' && chars[i] <= '9'){
                tmp += chars[i];
            }else{
                //操作符，临时数字存入output
                if(!tmp.isEmpty()){
                    output.add(tmp);
                    tmp = "";
                }
                if(chars[i] == '('){ //左括号，优先级最高，压入operators堆栈
                    ops.add(chars[i]);
                }else if(chars[i] == ')'){ //如果是右括号，将operators堆栈操作符出栈，直到左括号，操作符压入output堆栈
                    while(!ops.isEmpty()){
                        Character c = ops.pop();
                        if(c == '('){
                            break;
                        }else {
                            output.add(c.toString());
                        }
                    }
                }else if(chars[i]=='#'){ //终止符，operators压入output
                    while (!ops.isEmpty()){
                        output.add(ops.pop().toString());
                    }
                }else { //其他操作符，按优先级操作
                    while(!ops.isEmpty()){
                        if(ops.peek() != '(' && operatorLevel.get(ops.peek()) >= operatorLevel.get(chars[i])){ //优先级更高，operators出栈，压入output
                            output.add(ops.pop().toString());
                        }else{
                            break;
                        }
                    }
                    ops.add(chars[i]);
                }
            }
        }
        return output;
    }

    public static int calculateRPN(LinkedList<String> tokens){
        //System.out.println(tokens.toString());
        Deque<Integer> stack = new LinkedList<>();
        for (String token : tokens) {
            char c = token.charAt(0);
            if (!isOpe(token)) {
                stack.addFirst(stoi(token));
            } else if (c == '+') {
                stack.push(stack.pop() + stack.pop());
            } else if (c == '-') {
                stack.push(- stack.pop() + stack.pop());
            } else if (c == '*') {
                stack.push( stack.pop() * stack.pop());
            } else {
                int num1 = stack.pop();
                int num2 = stack.pop();
                stack.push( num2/num1);
            }
        }
        return stack.pop();
    }

    private static boolean isOpe(String s) {
        return s.length() == 1 && s.charAt(0) <'0' || s.charAt(0) >'9';
    }
    private static int stoi(String s) {
        return Integer.valueOf(s);
    }
}